Generally, encoding is a process that a transmitting side performs a data processing for a receiving side to restore original data despite errors caused by signal distortion, loss and the like while the transmitting side transmits data via a communication channel. And, decoding is a process that the receiving side restores the encoded transmitted data into the original data.
Recently, many attentions are paid to an encoding method using an LDPC code. The LDPC code is a linear block code having low density since most of elements of a parity check matrix H are zeros, which was proposed by Gallager in 1962. It was difficult to implement the LDPC code that is very complicated due to the technological difficulty in those days. Yet, the LDPC code was taken into re-consideration in 1995 so that its superior performance has been verified. So, many efforts are made to research and develop the LPDC code. (Reference: [1] Robert G. Gallager, “Low-Density Parity-Check Codes”, The MIT Press, Sep. 15, 1963. [2] D. J. C. Mackay, Good error-correcting codes based on very sparse matrices, IEEE Trans. Inform. Theory, IT-45, pp. 399-431 (1999))
Since the number of 1s of the parity check matrix of the LDPC code is very small, decoding of the parity check matrix of the LDPC is enabled through repetition decoding in case of a large block size. If the block size becomes considerably large, the parity check matrix of the LDPC code shows the performance that approximates a channel capacity limit of Shannon like a turbo code.
The LDPC code can be explained by a (n−k)×n parity check matrix H. And, a generator matrix G corresponding to the parity check matrix H can be found by Equation 1.H·G=0  [Equation 1]
In an encoding/decoding method using an LDPC code, a transmitting side encodes input data by Equation 2 using the generator matrix G having a relation of Equation 1 with the parity check matrix H.x=G·s, where ‘x’ is a codeword and ‘s’ is inputted source data.  [Equation 2]
Lately, a method of encoding input data using the parity check matrix H is globally used instead of the generator matrix G. Hence, as mentioned in the foregoing description, the parity check matrix H is the most important element in the encoding method using the LDPC code.
The parity check matrix H, as shown in FIG. 1, is configured with a plurality of z×z permutation matrices or a zero matrix. Namely, Pij in FIG. 1 means the z×z permutation matrix or zero matrix.
A plurality of the permutation matrices can be formed by permutating at least one base permutation matrix according to a predetermined regularity. For instance, if a base permutation matrix is set to a z×z identity matrix, a plurality of permutation matrices can be generated from shifting all rows of the base permutation matrix in a specific direction by a predetermined interval, exchanging a specific row (or column) of the base permutation matrix for another random row (or column) of the base permutation matrix, rotating the base permutation matrix by a predetermined angle or the like.
Instead of expressing a plurality of the permutation matrices configuring the party check matrix H as a matrix, by previously determining types of a plurality of the permutation matrices according to the method or class of permutating the base permutation matrix, it is able to express the parity check matrix H as the types of a plurality of the permutation matrices. In the following description, the parity check matrix H expressed as the types of a plurality of the permutation matrices is defined as a base matrix Hb to use. The base matrix Hb has mb×nb dimensions. In this case, mb=(n−k)/z and nb=n/z. And, the parity check matrix H can be generated in a manner of replacing information (hereinafter called a permutation type) of the type of the permutation matrix corresponding to each element of the base matrix Hb by a permutation matrix corresponding to the permutation type and expanding the corresponding permutation matrix.
FIG. 2 is a diagram of an example of the base matrix Hb.
Referring to FIG. 2, a 5×5 identity matrix is used as a base permutation matrix. A plurality of permutation matrices are generated from shifting all rows of the base permutation matrix in a specific direction by a predetermined interval. In doing so, the permutation type of the base permutation matrix as the 5×5 identity matrix is set to ‘1’, the permutation type of the permutation matrix generated from shifting all rows of the base permutation matrix by one row is set to ‘2’, the permutation type of the permutation matrix generated from shifting all rows of the base permutation matrix by two rows is set to ‘3’, the permutation type of the permutation matrix generated from shifting all rows of the base permutation matrix by three row is set to ‘4’, and the permutation type of the permutation matrix generated from shifting all rows of the base permutation matrix by five rows is set to ‘5’. Thus, the parity check matrix H is expressed as the permutation types. In FIG. 2, ‘0’ means a 5×5 zero matrix. IF the parity check matrix H is expressed as the permutation types, it is able to save the memory for storing the parity check matrix H. In FIG. 2, the permutation type is exemplarily expressed as an integer. Yet, the permutation type can be expresses in various ways.
Assuming that the base matrix Hb is divided into two parts (Hb)d and (Hb)p, the part (Hb)p can employ a block dual diagonal matrix as shown in FIG. 2. In the block dual diagonal matrix, a main diagonal and a diagonal beneath or directly above the main diagonal include identity matrices and the rest include zero matrices.
In case of using the block dual diagonal matrix as the part (Hb)p, a plurality of columns each having a weight of 1 is generated in the parity check matrix H. Namely, as a last column of the part (Hb)p is configured with one 5×5 identity matrix and a 5×5 zero matrix, five columns each having the weight of 1 are generated in aspect of the parity check matrix H. In the substantial encoding/decoding method using the LDPC code, since a matrix having dimensions considerably greater than the 5×5 dimensions is used as the base permutation matrix, the parity check matrix H includes more columns each having the weight of 1 than the example of FIG. 2. Hence, the operations for the encoding/decoding are complicated to considerably degrade encoding/decoding performance.